package stack_queue;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 347.前 K 个高频元素
 * Comparator接口说明
 * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
 * 对于队列：排在前面意味着往队头靠
 * 对于堆（使用PriorityQueue实现）：
 * 从队头到队尾按从小到大排就是最小堆（小顶堆）
 * 从队头到队尾按从大到小就是最大堆（大顶堆）-->队头元素相当于堆的根节点
 *
 * @author Api
 * @date 2023/10/18 23:52
 */
public class Code347_TopKHighFrequencyElements {

    //==================================================================================================================
    //解法1：基于大顶堆实现
    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // key为数组元素值，value为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //优先级队列中存储二元组（num,cnt），cnt表示元素值num在数组中的出现次数
        // 出现次数按从队头到队尾的顺序是从大到小排，出现次数最多的在队头（相当于大顶堆）
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //大顶堆需要对所有元素进行排序
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }

    //==================================================================================================================
    //解法2：基于小顶堆实现
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 在优先级队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        // 出现次数按从队头到队尾的顺序是从小到大排，出现次数最低的在队头（相当于小顶堆）
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序
            if (pq.size() < k) { // 小顶堆元素个数小于k时，直接加
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) {
                    {//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                        pq.poll(); // 弹出队头（小根堆的根节点），即把堆里出现次数最少的那个删除，留下的就是出现次数多的了
                        pq.add(new int[]{entry.getKey(), entry.getValue()});
                    }
                }
            }
        }
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }

    //==================================================================================================================
    //简化版代码
    public int[] topKFrequent(int[] nums, int k) {
        // 优先级队列，为了避免复杂 api 操作，pq 存储数组
        // lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从大到小，o2 - o1 反之
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k]; // 答案数组为 k 个元素
        Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> x : map.entrySet()) { // entrySet 获取 k-v Set 集合
            // 将 kv 转化成数组
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            pq.offer(tmp);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll()[0]; // 获取优先队列里的元素
        }
        return res;
    }
}
